import java.util.Iterator;

public class RandomQueue<Item> implements Iterable {

    public static void main(String args[])
    {
        // Build a queue containing the Integers 1,2,…,6:
        RandomQueue<Integer> Q= new RandomQueue<Integer>();
        for (int i = 1; i < 7; ++i) Q.enqueue(new Integer(i));

        // Print 30 die rolls to standard output
        StdOut.print("Some die rolls: ");
        for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
        StdOut.println();

        // Let’s be more serious: do they really behave like die rolls?
        int[] rolls= new int [10000];
        for (int i = 0; i < 10000; ++i)
        rolls[i] = Q.sample().intValue();
        StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
        StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
        StdStats.stddev(rolls));

        // Let’s look at the iterator. First, we make a queue of colours:
        RandomQueue<String> C= new RandomQueue<String>();
        C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow");

        Iterator I= C.iterator();
        Iterator J= C.iterator();

        StdOut.print("Two colours from first shuffle: ");
        StdOut.print(I.next()+" ");
        StdOut.print(I.next()+" ");

        StdOut.print("\nEntire second shuffle: ");
        while (J.hasNext()) StdOut.print(J.next()+" ");

        StdOut.print("\nRemaining two colours from first shuffle: ");
        StdOut.print(I.next()+" ");
        StdOut.println(I.next());
    }

    private Item[] q = (Item[]) new Object[2];
    private int N = 0;

    public boolean isEmpty(){
        return q.length==0;
    }

    public int size(){
        return q.length;
    }

    public void enqueue(Item item){
        if(N == q.length) resize(2 * q.length);
        q[N++] = item;
    }

    private void resize(int size){
        Item[] newArr = (Item[]) new Object[size];
        for(int i=0; i < N; i++)
            newArr[i] = q[i];
        q = newArr;
    }

    // return (but do not remove) an element
    public Item sample(){
        return q[N==1 ? 0 : StdRandom.uniform(N)];
    }

    //remove and return a random item
    public Item dequeue(){
        if(N==1) return q[--N];
        int r = StdRandom.uniform(N);
        Item out = q[r];
        q[r] = q[N-1];
        if(--N<(q.length/4)) resize(q.length/4);
        return out;
    }

    public Iterator<Item> iterator() {
        return new RandomQueueIterator<Item>();
    }

    public class RandomQueueIterator<Item> implements Iterator<Item> {
        private RandomQueue s;
        
        public RandomQueueIterator(){
            s = new RandomQueue<Item>();
            for(int i=0; i<N; i++)
                s.enqueue(q[i]);
        }

        public boolean hasNext() {
            return s.N>0;
        }
        
        public Item next()
        {
            return (Item) s.dequeue();
        }

        public void remove()
        {
            throw new UnsupportedOperationException("Not supported.");
        }
    }
}